import java.util.HashMap;

class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;

    public DLinkedNode() {

    }

    DLinkedNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache {

    int capacity;
    HashMap<Integer, DLinkedNode> map;
    DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode res = map.get(key);
        if (res == null) {
            return -1;
        }
        removeNode(res);
        addToHead(res);
        return res.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        if (node == null) {
            node = new DLinkedNode(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                DLinkedNode t = tail.prev;
                removeNode(t);
                map.remove(t.key);
            }
        } else {
            node.value = value;
            removeNode(node);
            addToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}
